package com.arron.algorithm.leetcodetop100.回溯;

import java.util.ArrayList;
import java.util.List;


/**
 *  注意，此题和最长回文字串类似
 *   @see com.arron.algorithm.leetcodetop100.动态规划.子序列or子数组.最长回文子串
 */
public class 分割回文串 {

    List<List<String>> res;



    public List<List<String>> partition(String s) {
        res = new ArrayList<>();

        // 表示 s[i...j] 是否是回文字串
        boolean[][] mem = new boolean[s.length()][s.length()];

        for (int i = 0; i < s.length(); i++) {
            mem[i][i] = true;
        }

        for (int len = 2; len <= s.length(); len++) {

            for (int i = 0; i < s.length(); i++) {

                int j = i+len-1;

                if (j >= s.length()){
                    break;
                }
                if (s.charAt(i) == s.charAt(j)){

                    if (len == 2){
                        mem[i][j] = true;
                    }else {
                        mem[i][j] = mem[i+1][j-1];
                    }
                }else {
                    mem[i][j] = false;
                }
            }
        }



        dfs(s,new ArrayList<>(),0,mem);
        return res;
    }



    public void  dfs(String s,List<String> splitList,int start,boolean[][] mem){


        if (start == s.length()){

            res.add(new ArrayList<>(splitList));

            return;
        }

        for (int len = 1; start+len <= s.length(); len++) {

            // 判断是否是回文字串
            if (!mem[start][start+len-1]){
                continue;
            }

            String substring = s.substring(start, start + len);


            splitList.add(substring);

            dfs(s,splitList,start+len,mem);

            splitList.remove(splitList.size()-1);
        }

    }


    public boolean valid(String s){
        if (s.length() == 1){
            return true;
        }
        int left = 0;
        int right = s.length()-1;

        while (left<right){

            if (s.charAt(left) != s.charAt(right)){
                return false;
            }

            left++;
            right--;

        }
        return true;
    }

    public static void main(String[] args) {

        分割回文串 split = new 分割回文串();

        String s =  "aab";

        List<List<String>> partition = split.partition(s);


        for (List<String> strings : partition) {
            System.out.println(strings);
        }

    }




}
